

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    vector<vector<int>> generateMatrix1(int n)
    {
        int leftCol = 0, rightCol = n - 1;
        int topRow = 0, bottomRow = n - 1;
        vector<vector<int>> res(n, vector<int>(n));

        for (int i = 1; i <= n * n;)
        {
            for (int j = leftCol; j <= rightCol; ++j)
            {
                res[topRow][j] = i++;
            }
            ++topRow;

            for (int j = topRow; j <= bottomRow; ++j)
            {
                res[j][rightCol] = i++;
            }
            --rightCol;

            for (int j = rightCol; j >= leftCol; --j)
            {
                res[bottomRow][j] = i++;
            }
            --bottomRow;

            for (int j = bottomRow; j >= topRow; --j)
            {
                res[j][leftCol] = i++;
            }
            ++leftCol;
        }

        return res;
    }

    vector<vector<int>> generateMatrix2(int n)
    {
        int leftCol = 0, rightCol = n - 1;
        int topRow = 0, bottomRow = n - 1;
        vector<vector<int>> res(n, vector<int>(n));

        for (int i = 1, index = 0; i <= n * n;)
        {
            for (index = leftCol; index <= rightCol; ++index)
            {
                res[topRow][index] = i++;
            }
            ++topRow;

            for (index = topRow; index <= bottomRow; ++index)
            {
                res[index][rightCol] = i++;
            }
            --rightCol;

            for (index = rightCol; index >= leftCol; --index)
            {
                res[bottomRow][index] = i++;
            }
            --bottomRow;

            for (index = bottomRow; index >= topRow; --index)
            {
                res[index][leftCol] = i++;
            }
            ++leftCol;
        }

        return res;
    }

    int findUnsortedSubarray1(vector<int>& nums)
    {
        int res = 0, n = nums.size();
        vector<int> tmp = nums;

        sort(tmp.begin(), tmp.end());
        for (int beg = 0, end = n - 1;;)
        {
            while (beg < n && nums[beg] == tmp[beg])
            {
                ++beg;
            }

            while (end >= 0 && nums[end] == tmp[end])
            {
                --end;
            }

            if (beg < end)
            {
                res = end - beg + 1;
                break;
            }
        }

        return res;
    }

    int findUnsortedSubarray2(vector<int>& nums)
    {
        int n = nums.size();
        int leftMin = -1, rightMax = n;
        int mini = INT_MAX, maxi = INT_MIN;

        for (int beg = n - 1, end = 0; beg >= 0 && end < n; --beg, ++end)
        {
            if (nums[beg] <= mini)
                mini = nums[beg];
            else
                leftMin = beg;

            if (nums[end] >= maxi)
                maxi = nums[end];
            else
                rightMax = end;
        }

        if (-1 == leftMin || n == rightMax)
            return 0;
        else
            return rightMax - leftMin + 1;
    }

    int findUnsortedSubarray3(vector<int>& nums)
    {
        if (is_sorted(nums.begin(), nums.end()))
            return 0;

        int n = nums.size();
        int beg = 0, end = n - 1;
        vector<int> tmp = nums;

        sort(tmp.begin(), tmp.end());

        while (beg < n && nums[beg] == tmp[beg])
        {
            ++beg;
        }
        while (end >= 0 && nums[end] == tmp[end])
        {
            --end;
        }

        return end - beg + 1;
    }
};

void Test1()
{
    vector<int> v = {2, 6, 4, 8, 10, 9, 15};

    Solution().generateMatrix(3);
    Solution().findUnsortedSubarray1(v);
}

int main()
{
    Test1();

	return 0;
}